/*
2021-7-19
https://leetcode-cn.com/problems/maximum-genetic-difference-query/
*/
typedef pair<int,int> PII;
const int N=1e5+10,M=3e5+10;
int h[N],ne[N],e[N],idx1;
int son[M][2],cnt[M],idx2;

class Solution {
public:
    unordered_map<int,vector<PII>>qs;

    void add(int a,int b)
    {
        e[idx1]=b,ne[idx1]=h[a],h[a]=idx1++;
    }

    void insert(int u,int v)
    {
        int p=0;
        for(int i=31;i>=0;i--)
        {
            int j=u>>i&1;
            if(!son[p][j]) son[p][j]=++idx2;
            p=son[p][j];
            cnt[p] +=v;
        }
    }

    int query(int x)
    {
        int p=0,res=0;
        for(int i=31;i>=0;i--)
        {
            int j=x>>i&1;
            if(cnt[son[p][!j]])
            {
                res+=1<<i;
                p=son[p][!j];
            }
            else p=son[p][j];
        }
        return res;
    }
    void dfs(int u,vector<int> &res)
    {
        insert(u,1);
        if(qs.count(u))
            for(auto& q : qs[u])
            {
                res[q.second]=query(q.first);
            }

        for(int i=h[u];~i;i=ne[i])
            dfs(e[i],res);
        insert(u,-1);
    }
    vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
    int root;
    memset(h,-1,sizeof h);
    memset(cnt,0,sizeof cnt);
    memset(son,0,sizeof son);
    idx1=0,idx2=0;

    for(int i=0;i<parents.size();i++)
    {
        if(parents[i]==-1) root=i;
        else add(parents[i],i);
    }

    for(int i=0;i<queries.size();i++)
    {
        int node=queries[i][0],val=queries[i][1];
        qs[node].push_back({val,i});
    }

    vector<int> res(queries.size());

    dfs(root,res);

    return res;
    }
};
